package cn.fxzhang.leetcode.contest.week236;

public class P5728_Minimum_Sideway_Jumps {

    public int minSideJumps(int[] obstacles) {
        // 将赛道改成0-2
        for (int i=0; i<obstacles.length; i++) {
            obstacles[i]--;
        }
        int MAX = (int) (5*1e5+1);
        int n = obstacles.length;
        int[][] f = new int[n][3];
        f[0][0] = 1;
        f[0][2] = 1;
        for (int i=1; i<n; i++){
            // 从前一格跳过来
            for (int j=0; j<3; j++){
                f[i][j] = f[i-1][j];
            }
            if (obstacles[i] != -1){
                f[i][obstacles[i]] = MAX;
            }
            f[i][0] = min(f[i][0], f[i][1]+1, f[i][2]+1);
            f[i][1] = min(f[i][1], f[i][0]+1, f[i][2]+1);
            f[i][2] = min(f[i][2], f[i][0]+1, f[i][1]+1);
            if (obstacles[i] != -1){
                f[i][obstacles[i]] = MAX;
            }
        }
        return min(f[n-1][0], f[n-1][1], f[n-1][2]);
    }

    private int min(int a, int b, int c){
        return Math.min(Math.min(a,b),c);
    }
}
